package algorithm.leetcode.I1to100;

/**
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数
 * 允许的三种操作: 增加,删除,替换
 *
 * 输入：word1="horse",word2="ros"
 * 输出：3
 *
 * dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, if word[i] != word[j]
 *            dp[i-1][j-1], else
 * 这个递推关系可以看成:
 *    如果两个指针指向的字母相同,那么变换次数就等于各自向前移动一位的变换次数,即上面的else情况
 *    否则,从允许的三个操作中找一个最小的,删除对应dp[i][j-1],增加对应dp[i-1][j],替换对应dp[i-1][j-1]
 */

//    | "" | r | o | s
// ---+----+---+---+---
// "" | 0  | 1 | 2 | 3
//  h | 1  | 1 | 2 | 3
//  o | 2  | 2 | 1 | 2
//  r | 3  | 2 | 2 | 2
//  s | 4  | 3 | 3 | 2
//  e | 5  | 4 | 4 | 3


public class Q72 {

    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        for (int i = 0; i <= word1.length(); i++) {
            for (int j = 0; j <= word2.length(); j++) {
                if (j == 0) dp[i][j] = i; // 填充第一列
                else if (i == 0) dp[i][j] = j; // 填充第一行
                else if (word1.charAt(i-1) != word2.charAt(j-1)) dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                else dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[word1.length()][word2.length()];
    }

    public static void main(String[] args) {
        Q72 q72 = new Q72();
        System.out.println(q72.minDistance("horse", "ros"));
    }
}
